/*
题目链接：https://leetcode.cn/problems/count-numbers-with-unique-digits/description/
357. 统计各位数字都不同的数字个数-中等
完成日期：2024/10/3
数位DP
*/
class Solution {
public:
    int a[20]={0};
    long long dp[20][1<<11];
    long long dfs(int po,int s,bool l,bool le){
        if(po==-1)return 1;
        if(dp[po][s]!=-1)return dp[po][s];
        int up=l?a[po]:9;
        long long ans=0;
        for(int i=0;i<=up;++i){
            if(le&&i==0)ans+=dfs(po-1,s,l&&i==up,true);
            else{
                if(s&(1<<(i)))continue;
                else ans+=dfs(po-1,s|(1<<(i)),l&&i==up,le&&i==0);
            }
        }
        dp[po][s]=ans;
        return ans;
    }
    
    long long solve(long long x){
        int pos=0;
        while(x){
            a[pos++]=x%10;
            x/=10;
        }
        return dfs(pos-1,0,true,true);
    }
    int countNumbersWithUniqueDigits(int n) {
        long long x=1;
        memset(dp,-1,sizeof dp);
        while(n){
            x*=10;
            n--;
        }
        return solve(x-1);
    }
};
